package com.LeeCode;

import java.util.HashMap;
import java.util.Map;

/**
 * LFU 缓存
 */

public class Code460 {
    public static void main(String[] args) {

    }

    class LFUCache {
        class Node {
            int key, value, freq = 1;

            Node prev, next;

            public Node(int key, int value) {
                this.key = key;
                this.value = value;
            }
        }

        private final int capacity;
        private final Map<Integer, Node> keyToNode = new HashMap<>();
        private final Map<Integer, Node> freqToDummy = new HashMap<>();
        private int minFreq;

        public LFUCache(int capacity) {
            this.capacity = capacity;
        }

        public int get(int key) {
            Node node = getNode(key);
            if (node == null) {
                return -1;
            }
            return node.value;
        }

        public void put(int key, int value) {
            Node node = getNode(key);
            if (node != null) {
                node.value = value;
                return;
            }

            if (keyToNode.size() == capacity) {
                Node dummy = freqToDummy.get(minFreq);
                Node backNode = dummy.prev;
                keyToNode.remove(backNode.key);
                remove(backNode);
                if (dummy.prev == dummy) {
                    freqToDummy.remove(minFreq);
                }
            }

            node = new Node(key, value);
            keyToNode.put(key, node);
            pushFront(1, node);
            minFreq = 1;
        }

        private Node getNode(int key) {
            if (!keyToNode.containsKey(key)) {
                return null;
            }
            Node node = keyToNode.get(key);
            remove(node);
            Node dummy = freqToDummy.get(node.freq);

            if (dummy.prev == dummy) {
                freqToDummy.remove(node.freq);
                if (minFreq == node.freq) {
                    minFreq++;
                }
            }
            pushFront(++node.freq, node);
            return node;
        }

        private void remove(Node node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }

        private void pushFront(int freq, Node node) {
            Node dummy = freqToDummy.computeIfAbsent(freq, k -> newList());
            dummy.next.prev = node;
            node.next = dummy.next;

            dummy.next = node;
            node.prev = dummy;
        }

        private Node newList() {
            Node dummy = new Node(0, 0);
            dummy.next = dummy;
            dummy.prev = dummy;
            return dummy;
        }
    }
}
